#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct Node* Tree;
struct Node {
	ElementType element;
	Tree left;
	Tree right;
};
typedef struct Sqlist* List;
struct Sqlist {
	ElementType* arr;
	int len;
	int capacity;
};

List creatlist() {
	List L=malloc(sizeof(struct Sqlist));
	if (L == NULL) {
		perror("malloc");
		return NULL;
	}
	L->arr = malloc(20 * sizeof(ElementType));
	if (L->arr == NULL) {
		perror("malloc");
		return NULL;
	}
	L->len = 0;
	L->capacity = 20;
	return L;
}

Tree MakeEmpty(Tree T) {
	if (T!=NULL) {
		MakeEmpty(T->left);
		MakeEmpty(T->right);
		free(T);
	}
	return NULL;
}

Tree Insert(Tree T, ElementType x) {
	if (T == NULL) {
		T = malloc(sizeof(struct Node));
		if (T == NULL) {
			perror("malloc");
			return NULL;
		}
		T->element = x;
		T->left = NULL;
		T->right = NULL;
	}
	else if (x < T->element) {
		T->left=Insert(T->left, x);
	}

	else if (x > T->element) {
		T->right = Insert(T->right, x);
	}
	return T;
}

void Digui(Tree T, List L) {
	if (T != NULL) {
		Digui(T->left,L);
		L->arr[L->len++] = T->element;
		Digui(T->right, L);
	}
}

void IsOrderBST(Tree T,List L) {
	int i = 0;
	Digui(T, L);
	for (i = 0; i < L->len; i++) {
		printf("%d ", L->arr[i]);
	}
}

int main() {
	Tree T;
	T=MakeEmpty(NULL);
	T = Insert(T, 5);
	T = Insert(T, 3);
	T = Insert(T, 2);
	T = Insert(T, 4);
	T = Insert(T, 7);
	T = Insert(T, 6);
	T = Insert(T, 9);

	List L=creatlist();
	IsOrderBST(T, L);
	return 0;
}

